Codeforces Round 637 Div2 A~D题解

A. Nastya and Rice
题目大意:有nn个石头,每个石头的重量在[ab,a+b][a - b, a + b]之间,问所有石头的重量总和有没有可能在[cd,c+d][c - d,c + d]之间,输出正确与否即可。
数据范围:intint范围内
解法:直接判断最大值和最小值有没有可能在区间内即可。

B. Nastya and Door
题目大意:定义山峰是一个区间里除了首尾两个端点之外的,满足值大于左右两边的值的位置。给定区间长度kk,求出以LL开始的长度为kk的区间里最多包含几个山峰的数量,并加一作为答案,以及起始的坐标LL。如果有相同的则取最左端的。
数据范围:intint范围内
解法:前缀和求区间内有多少个满足条件的,特别判断一下端点有没有被计入答案,如果有则挖掉即可。

C. Nastya and Strange Generator
题目大意:给你一个排列数生成器,他按如下的规则产生一个排列:
①当前在第ii步时,放的数就是ii
②对每个1jn1 \leq j \leq n计算出RjR_jRjR_j表示jj以及jj之后最近的空位的下标是多少,如果没有则不记。
③在所有的RjR_j里选出合法且数量最多的,放入这个位置。
现给定一个排列,问这个排列是否有可能是这个生成器产生的,只需要输出正确性。
数据范围:1N1051 \leq N \leq 10^5

解法:生成所有合法序列显然不可行,考虑每个点是不是合法的。
首先,数字是按顺序放入序列的,那么整个序列的正确性应该是与放的顺序相关的,故应该从这里入手。
假设11是放在ii位置上的,放进去之后会使得下一步的RjR_j序列里,ii上的RR变成i+1i + 1,这意味着22只能放在i+1i + 1这个位置上,除非11后面没位置了。因此可以推出这个题的结论就是:整个序列如果有上升的部分,那么他一定是连续上升的,否则不正确。最后遍历做个判断就可以了。
代码:

const int N = 1e5+7;
int a[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
    	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
    	int ok = 1;
    	for(int i = 1;i <= n - 1;++i)
    	{
    		if(a[i] < a[i + 1] && a[i] + 1 != a[i + 1])
    		{
    			ok = 0;
    			break;
    		}
    	}
    	if(!ok)	puts("No");
    	else puts("Yes");
    }
    return 0;
}

D. Nastya and Scoreboard
题目大意:有nn个灯,每个灯是有77个灯管工作显示数字的,但是现在灯管被砸坏了kk个,问:恰好点亮kk个灯管之后,能得到的最大数字是多少。要求数字合法,且允许前导0存在。
数据范围:1n20001 \leq n \leq 2000
0k20000 \leq k \leq 2000
解法:一个很直接的想法就是dpdp
设状态f[i][j]f[i][j]表示前ii个里开上了jj个灯管之后,能获得的最大的数字是多少,然而这个做法很快就可以被推翻掉,因为时间复杂度上过不去,枚举nnkk的复杂度还要带上一个比较字符串大小的nn,这说明这个思路就有问题。但是不代表dpdp不行,实际上可以退而求其次,只保留可行性,而不直接求出具体方案。在求的了当前这个状态的可行性之后,直接把方案构造出来就可以了。
状态:f[i][j]f[i][j]表示当前已经修完了ii号和之前的所有灯,已经用掉了jj个灯管,当前这个状态是否是可以合法的。
入口:f[0][0]=1f[0][0] = 1
出口:f[n][m]==1f[n][m] == 1代表有解,否则无解
转移:f[i][j]=f[i1][j]f[i][j] |= f[i - 1][j - 当前灯换成其他状态的代价]
但是这样还是不够,因为没有考虑到:恰好用完所有kk次开灯的机会这个条件。可以发现如果正着去考虑的话,整个方案到最后是不是合法的?不知道,因为之后构造方案的时候根本没办法在最后一步说能恰好把kk次机会用完。换个角度:入口是一个实际的点,他不应该是f[0][0]f[0][0]这个所有都没开的状态,而应该是f[n+1][k]f[n + 1][k]这个状态,如果初始只有f[n+1][m]f[n + 1][m]这个点是合法的,那么以他作为入口推得的所有状态显然最后一定会到达f[n+1][m]f[n + 1][m]这个表示恰好用完了所有灯管的状态,才是正确的。同时,出口也要变换一下,这个时候f[1][m]f[1][m]才是出口,如果这个状态不合法的话就说明没有合法方案,输出无解。
第一问就是一个可行性的dpdp
第二问是求出一个具体方案来,就比较好想了。直接从前往后遍历,优先满足前面最大的能得到的值。由于所有可行性的状态都是由f[n+1][m]f[n + 1][m]转移而来的,故最后一定会把kk推到00,输出方案即可。
代码:

typedef long long ll;
const int N = 2005;
int f[N][N];
const string table[13] = {"1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"};
int gdist(const string& a,const string& b)
{
	int res = 0;
	for(int i = 0;i < 7;++i)
	{
		if(a[i] == '1' && b[i] == '0')	return -1;
		if(a[i] == '0' && b[i] == '1')	++res;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m;cin >> n >> m;
	vector<string> a(n + 17);
	for(int i = 1;i <= n;++i)	cin >> a[i];
	f[n + 1][0] = 1;
	for(int i = n;i >= 1;--i)
		for(int k = 0;k <= 9;++k)
		{
			int w = gdist(a[i],table[k]);
			if(w == -1)	continue;
			for(int j = w;j <= m;++j)
				f[i][j] |= f[i + 1][j - w];
		}
	if(!f[1][m])
	{
		cout << -1;
		return 0;
	}
	string res;
	for(int i = 1;i <= n;++i)
	{
		for(int k = 9;k >= 0;--k)
		{
			int w = gdist(a[i],table[k]);
			// if(i == 1)	cout << w << endl;
			if(w != -1 && m >= w && f[i + 1][m - w])
			{
				m -= w;
				res += char(k + '0');
				break;
			}
		}
	}
	cout << res << endl;
    return 0;
}